알고리즘 정리

마지막 수정일: 2025. 05. 16.

순열(Permutation, Combination)

순열은 보통 재귀적으로 구현
알고리즘은 기본적으로 하나를 고정하고 나머지에서 n-1개의 순열을 또 구하는 것
permutation은 순서가 있으므로 고정된 값을 제외하고 나머지를 모두 봐야하고
combination은 순서가 없으므로 고정된 값 이후에 나오는 값으로만 진행(전에 나오는 애들은 이미 셌기 때문)\

Permutation

JAVASCRIPT

function permutation(arr, num){
	const res = [];
	if(num === 1) return arr.map((v) => [v]);
	arr.forEach((v, idx, arr) => {
		const rest = arr.filter((_, restIndex) => restIndex != idx);
		const combinations = combination(rest, num-1);
		const attach = combinations.map((combination) => [v,...combination]);
		res.push(...attach);
	})
	return res;
}

### Combination ``` javascript function combination(arr, num){ const res = []; if(num === 1) return arr.map((v) => [v]); arr.forEach((v, idx, arr) => { const rest = arr.slice(idx+1); const combinations = combination(rest, num-1); const attach = combinations.map((combination) => [v,...combination]); res.push(...attach); }) return res; } ```

## Heap 삽입, 삭제 : O(logn)\ 최대, 최소값 : O(1)\ 총 정렬을 하는데는 O(nlogn)으로 같지만 단순히 몇 개만 할 거라면 heap을 쓰는 게 효율적\

보통 우선순위큐를 구현하기 위해서 사용됨
예시는 최소 heap 구현\

JAVASCRIPT

class MinHeap {
  constructor(...args) {
    this.heap = [];
    if (args.length === 0) return;
    args.forEach((value) => this.insert(value));
  }

  // --- Helper methods ---
  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  get len() {
    return this.heap.length;
  }

  // --- Core methods ---
  insert(value) {
    this.heap.push(value);
    this._heapifyUp();
  }

  pop() {
    if (this.len === 0) return undefined;
    if (this.len === 1) return this.heap.pop();

    const min = this.peek();
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return min;
  }

  peek() {
    return this.heap.at(0) ?? null;
  }

  _heapifyUp() {
    let index = this.len - 1;

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[index] >= this.heap[parentIndex]) break;

      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  _heapifyDown() {
    let index = 0;

    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let smallestIndex = index;

      if (
        leftChildIndex < this.len &&
        this.heap[leftChildIndex] < this.heap[smallestIndex]
      ) {
        smallestIndex = leftChildIndex;
      }

      if (
        rightChildIndex < this.len &&
        this.heap[rightChildIndex] < this.heap[smallestIndex]
      ) {
        smallestIndex = rightChildIndex;
      }

      if (smallestIndex === index) break;

      this.swap(index, smallestIndex);
      index = smallestIndex;
    }
  }

  // debug method
  print() {
    console.log(this.heap);
  }
}

순열(Permutation, Combination)